package Stack;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/**
 *  题目 ：验证栈序列
 *  题目详解 ：
 *  给定pushed和popped两个序列，每个序列中的 值都不重复，
 *  只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false。
 */
public class P934 {
    /**
     *  核心思想 ：
     *  定义一个栈用来存放pushed数组中元素，同时popped数组中的元素，即使用弹栈将其弹出栈；
     *  结果 ：若是最后栈为空的话，即===》栈序列成立
     */
//    Deque<Integer> stack = new LinkedList<>();
//    public boolean validateStackSequences(int[] pushed, int[] popped) {
//        int i = 0,j = 0;
//        // 即，pushed数组中的元素数和popped数组中的元素数目应该是一致
//        int length = pushed.length;
//        /**
//         * 由于pushed数组中元素被遍历完，不算真正的结束；
//         * (1）尤其仅当popped数组中的元素也被遍历完才算真正结束[由于popped数组是弹栈操作，其必然是在pushed数组（入栈操作）之后结束]
//         * （2）当pushed数组中所有的元素都被压入栈中，但是popped数组还未匹配到，即代表结束
//         */
//        while(i <= length && j < length) {
//            // 当栈中不存在元素时，即不需要进行栈顶元素是否与popped数组中的元素一致
//            if (stack.isEmpty()) {
//                stack.push(pushed[i++]);
//                System.out.println("empty");
//            }
//            // 当栈顶元素与popped元素一致时
//            else if(popped[j] == stack.peek()){
//                System.out.println("pop" + stack.peek());
//                j++;
//                stack.pop();
//            }
//            // 当栈顶元素与popped元素不一致时
//            else {
//                // 为了避免当
//                if (i == length){
//                    // 方法一 ：直接跳出循环
//                    // break;
//                    // 方法二 ：将i++，使得其不满足while条件
//                    i++;
//                }
//                else {
//                    stack.push(pushed[i++]);
//                }
//                System.out.println("push" + stack.peek());
//            }
//        }
//        if(stack.isEmpty()){
//            return true;
//        }
//        return false;
//    }

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new ArrayDeque<>();
        int length = pushed.length;
        /**
         *  核心思想 ：
         *  即，每次使用pushed数组将一个值压入栈中时，就去popped数组中进行匹配，去查找是否存在能够弹栈的元素
         */
        for(int i = 0 , j = 0;i < length ; i++){
            // 即，只需要将pushed数组中所有元素压入栈中即可，若是栈顺序存在的话，栈会为空
            stack.push(pushed[i]);
            // （1）当栈不为空时，（2）同时popped数组中的元素匹配到栈顶元素时，即进行弹栈
            while(!stack.isEmpty() && popped[j] == stack.peek()){
                /**
                 * 注意 ：
                 * 若是在判断条件中写上i++时，每次进行判断时，都会进行i++（格外注意，此处不注意的话，容易出错）
                 */
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}
